import java.util.Stack;

public class Main {


    //最小栈
    // 分析可得必须要用到两个栈
    // 在MinStack中写


    // 栈的压入、弹出序列
    //解题思路
    //为两个数组分别定义两个下标变量 i j
    //每一次入栈的时候都要与popV数组里面的数进行比较
    // 比较成功了 出栈，i++ j++
    //
    public boolean isPopOrder (int[] pushV, int[] popV) {
       //分析就是，在入的时候可以出//

        //如 pushA：1 2 3 4 5
        //   popA： 4 5 3 2 1

        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]); //先放元素再比较
            while(j < popV.length && !stack.empty() && stack.peek().equals(popV[j])){
                stack.pop();  //一样了就弹出 ,还要考虑越界问题
                j++;
            }
        }
        return stack.empty(); //返回判断栈是否为空
    }



        //有效的括号,括号匹配

    //解题思路，只在数量上相同肯定是不行的
    // 把左括号压入栈中，遇到右括号的话就出栈进行匹配
    // 当 字符串遍历完了，并且栈空了就匹配成功了

    //有这几种情况
    // 左括号多：字符串遍历完成但是栈不空
    // 右括号多：字符串没完，栈空了
    // 不匹配
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        //遍历字符串
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            //判断是否是左括号
            if(ch=='('||ch=='{'||ch=='['){
                stack.push(ch);
            }else{
                //右括号的情况
                //先判断当前的栈空不空，因为会遇到第一个就是右括号的情况
                if(stack.empty()){
                    return false; // 说明右括号会多
                }
                char ch2 = stack.peek();//先不着急出栈，先查看一下第一个元素是否与右括号匹配
                // 这时的ch2是左括号,但是不知道是哪一个右括号所以先判断一下
                if(ch2 == '('&&ch == ')'||ch2 == '{'&&ch == '}'||ch2 == '['&&ch == ']'){
                    //匹配成功了就pop出去左括号

                    stack.pop();
                }else {
                    return false; // 不匹配
                }
            }
        }
        //字符串遍历完了，看栈空不空
        if(!stack.empty()){
            return false; //左括号多
        }
        //都遍历完了返回true
        return true;
    }

        // 逆波兰表达式求值
        public int evalRPN(String[] tokens) {
            Stack<Integer> stack = new Stack<>();
            //遍历栈
            for (String x: tokens) {
                if(!isOperation(x)){
                    //不是运算符的话入栈
                    stack.push(Integer.parseInt(x)); // 把x强制转换
                }else{
                    //是运算符的话出栈里面的两个元素
                    //栈顶在运算符右边，下一个在运算符左边
                    // 不能调换顺序
                    // 第一个弹出去的数据为 num2 ， 第二个为 num1

                    int num2 = stack.pop(); // 第一个数据
                    int num1 = stack.pop(); // 第二个数据

                    //接下来判断是哪个操作符
                    switch(x){
                        case "+":
                            stack.push(num1+num2);//计算后重新压栈，后面操作同理
                            break;
                        case "-":
                            stack.push(num1-num2);//计算后重新压栈，后面操作同理
                            break;
                        case "*":
                            stack.push(num1*num2);//计算后重新压栈，后面操作同理
                            break;
                        case "/":
                            stack.push(num1/num2);//计算后重新压栈，后面操作同理
                            break;
                    }
                }
            }
            return stack.pop();//返回当前栈中的元素
        }

        private boolean isOperation(String x){
            // 判断x是否是运算符
            if(x.equals("+")||x.equals("-")||x.equals("*")||x.equals("/")){
                return true;
            }
            return false;
        }

    public static void main2(String[] args) {
        // 模拟实现一个栈
        MyStack stack = new MyStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        //出栈
        // 用pop获取
        Integer a = stack.pop(); //3
        System.out.println(a);
        // 用peek获取,peek不是出栈，而是返回查看栈顶元素
        Integer b = stack.peek(); //2
        System.out.println(b);
        Integer b2 = stack.peek(); //2
        System.out.println(b2);
        //判断栈是否为空
        System.out.println(stack.isEmpty());
    }
    public static void main1(String[] args) {
        System.out.println("Hello world!");
        //****栈和队列****
        //栈的特点：先进后出
        //源码栈里面只有五个方法
        Stack<Integer> stack = new Stack<>();
        //入栈/压栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        //出栈
        // 用pop获取
        Integer a = stack.pop(); //3
        System.out.println(a);
        // 用peek获取,peek不是出栈，而是返回查看栈顶元素
        Integer b = stack.peek(); //2
        System.out.println(b);
        Integer b2 = stack.peek(); //2
        System.out.println(b2);
        //多少个元素
        System.out.println(stack.size()); // 2
        //判断栈是否为空
        System.out.println(stack.empty());

    }
}